The first use of molecular biology for the solution of a combinatorial problem was published by Adleman in 1994 (Adleman, 1994, Science 266: 1021-1024). Adleman used DNA molecules to solve an example of a directed Hamiltonian path problem. A directed graph with a finite number of vertices (v.sub.in -v.sub.out) is said to have a Hamiltonian path if there exists a sequence of one-way edges (i.e., paths) that begins at v.sub.in and ends at v.sub.out, and enters every other vertex only once. To solve this problem, Adleman synthesized a series of DNA oligonucleotides representing the vertices and edges of a graph containing six vertices, and then combined the oligonucleotides in a single ligation reaction. In this way, Adleman generated DNA molecules representing random paths through the graph. He then used a series of molecular biological techniques to (1) select only those paths (i.e., DNA molecules) which begin with v.sub.in and end in v.sub.out ; (2) select only those paths that enter 6 vertices (since the graph has 6 vertices); and (3) select only those paths that enter all of the vertices at least once. These procedures, which employed techniques such as polymerase chain reaction ("PCR") and affinity-labeled magnetic bead separation, required a total of approximately seven days of laboratory work.
Recently, this approach has been extended by Lipton to solve a "satisfaction" problem (Lipton, 1995, Science 268: 542). Lipton, essentially using Adleman's techique to formulate all possible solutions of a compound Boolean formula, demonstrated that it may in theory be possible to use molecular biology to extract results that would satisfy the Boolean expression. There are several problems associated with Lipton's approach. First, the necessary laboratory operations would scale linearly with the amount of input, and as the complexity of the problem increases would quickly become impractical to execute. Second, Lipton's formulation is for idealized DNA, and for the use of idealized laboratory operations which he assumes can be expeditiously carried out. Lipton in fact admits that his model of how DNA behaves is "simple and idealized" and "ignores many complex known effects".
The methods of Adleman and Lipton demonstrate that problems corresponding to Boolean formulas can be solved using DNA molecules. However, their methods suffer from a number of severe limitations in addition to those described above.
The methods of Adleman and Lipton cannot be used to solve problems which, given a particular set of input, require a single specific solution. Their methods are directed to search problems, which may be solved by using the input to generate a multitude of possible solutions, and then searching for the desired output. In contrast, binary operations, such as addition, require a control mechanism that produces the single correct solution; two plus two can only equal four.
Using the methods of Adleman and Lipton, the laboratory work required to arrive at an answer to a given problem is technically extremely cumbersome, and essentially involves the purification of a correct molecular result from a random population of erroneous results generated by the computation reaction.
Computers perform binary operations by "bit-flipping", wherein a computer bit may be turned (or "flipped") on and off. The ability to "bit-flip" enables a computer to perform a series of steps, not in a random manner, but with direction. The ability of a bit to be "on" or "off" is analogous to the binary system of numbers, which has only two integers, 1 and 0. When a computer performs addition of the binary numbers 0 and 1, a bit representing the first number, 0, is off; when the second number, 1, is added, the computer effectively "flips" the bit, and like throwing a switch, advances it to the "on" position, to yield the correct sum, 1. Similarly, if the first number is 1 (and therefore the bit is "on") but the second number to be added is also 1, the computer flips the bit to the next position, 0 (i.e., "off"), and "carries the one" (by an algorithm discussed below) to arrive at the correct sum, which is 10. Thus, through bit-flipping, the computer is able to arrive at the correct solution to an addition problem.
The methods of Adleman and Lipton have no such capability. At most, in order to solve an addition problem, these methods would ligate together DNA molecules representing all possible solutions in a "computation reaction", and then it would be necessary to select the correct solution, a project potentially as tedious as if the computation reaction had not been performed in the first place. Their methods suffer similar shortcomings when applied to other operations where nonrandom associations between data points are required.